/*
 * @lc app=leetcode.cn id=547 lang=cpp
 * @lcpr version=30204
 *
 * [547] 省份数量
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class UnionFindSet
{
public:
	UnionFindSet(int n)
	{
		_v.resize(n, -1);
	}

	int FindRoot(int x)
	{
		while (_v[x] >= 0)
		{
			x = _v[x];
		}
		return x;
	}

	bool Union(int x1, int x2)
	{
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);
		
		if (root1 == root2)	// x1 x2 在一颗树中
		{
			return false;
		}

		_v[root1] += _v[root2];
		_v[root2] = root1;

		return true;
	}

    size_t Size()
    {
        int n = 0;
        for(auto e : _v)
        {
            if(e < 0)
            {
                ++n;
            }
        }
        return n;
    }

private:
	vector<int> _v;
};
class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        // 这题的本质就是看元素组成几棵树
        // 并查集
        UnionFindSet ufs(isConnected.size());
        for(int i = 0; i < isConnected.size(); ++i)
        {
            for(int j = 0; j < isConnected[i].size(); ++j)
            {
                if(isConnected[i][j] == 1)
                {
                    ufs.Union(i, j);
                }
            }
        }
        return ufs.Size();
    }
};
// @lc code=end



/*
// @lcpr case=start
// [[1,1,0],[1,1,0],[0,0,1]]\n
// @lcpr case=end

// @lcpr case=start
// [[1,0,0],[0,1,0],[0,0,1]]\n
// @lcpr case=end

 */

